package main

import (
	"fmt"
	"math"
)

/*
    超级丑数
编写一段程序来查找第 n 个超级丑数。
超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。

示例:
输入: n = 12, primes = [2,7,13,19]
输出: 32
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
 */

func nthSuperUglyNumber(n int, primes []int) int {
	dp := []int{1}
	position := make([]int, len(primes)) //记录每个质数的指针位置

	for len(dp) < n {
		min := minVal(dp, primes, position) //每次挑选出最小的
		if dp[len(dp)-1] < min {            //防止重复值的情况
			dp = append(dp, min)
		}
	}
	return dp[n-1]
}

func minVal(dp, primes, position []int) int { //返回最小值，并把相应的指针后移
	min_i, min_val := 0, math.MaxInt32
	for i, prime := range primes {
		if val := dp[position[i]] * prime; val < min_val {
			min_i, min_val = i, val
		}
	}
	position[min_i]++
	return min_val
}

func main() {
	fmt.Println(nthSuperUglyNumber(12, []int{2,7,13,19}))
}
